//1.me-->两趟扫描实现
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        
        ListNode* act = head;
        int target = 0;
        while(act) {
            act= act->next;
            target++;
        }
        target -= n;
       
        int i = 0;
        ListNode ret(-1);
        ListNode*temp = &ret;
        temp->next = head;
        
        while(temp) {
            if(i == target) {
                temp->next = temp->next->next;
                break;
            }
            else {
                ++i;
                temp= temp->next;
            }
        }
        return ret.next;
    }
};

//2.栈
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        stack<ListNode*> stk;
        ListNode* cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            stk.pop();
        }
        ListNode* prev = stk.top();
        prev->next = prev->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};
//3.进阶：一趟扫描实现
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next; //先走n步
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next; //此时second位于倒数第n+1个节点，second->next保证不为nullptr(n>=1)，first保底先走一步
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};



